package me.algo.rec;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Objects;
import java.util.TreeSet;

/**
 * @author guozheng
 * @date 2024/5/10
 */
public class R3 {
    public static void main(String[] args) {
        var coins = new int[]{186,419,83,408};
        int amount = 6249;
        int i= coinChange(coins, amount);
        System.out.println(i);
    }

    /**
     * 硬币兑换
     * @param coins
     * @param amount
     * @return
     */
    public static int coinChange(int[] coins, int amount) {
        int max = amount + 1;
        int[] dp = new int[max];
        Arrays.fill(dp, max);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (coin <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }

    private static TreeSet<Integer> toSet(int[] coins) {
        TreeSet<Integer> cst = new TreeSet<>();
        for (int c : coins) {
            cst.add(c);
        }
        return cst;
    }

    public static List<List<Integer>> coinType(int[] coins, int amount) {
        if (Objects.isNull(coins) || coins.length == 0) {
            return new ArrayList<>();
        }
        LinkedList<Coin> que = new LinkedList<>();
        for (int c : coins) {
            if (c <= amount) {
                List<Integer> lst = new ArrayList<>();
                lst.add(c);
                Coin coin = new Coin(lst);
                que.addLast(coin);
            }
        }
        TreeSet<Integer> cs = toSet(coins);
        List<List<Integer>> rtn = new ArrayList<>();
        while (!que.isEmpty()) {
            Coin last = que.removeFirst();
            List<Integer> lst = last.lst();
            int sum = last.sum();
            int rem = amount - sum;
            if (rem == 0) {
                rtn.add(lst);
                continue;
            }

            for (int c : coins) {
                if (c < rem) {
                    List<Integer> nlst = new ArrayList<>(lst);
                    nlst.add(c);
                    Coin coin = new Coin(nlst);
                    que.addLast(coin);
                } else if (c == rem) {
                    List<Integer> nlst = new ArrayList<>(lst);
                    nlst.add(c);
                    rtn.add(nlst);
                }
            }
        }
        return rtn;
    }
    record Coin(List<Integer> lst, int sum) {
        public Coin(List<Integer> lst) {
            this(lst, sum(lst));
        }

        static int sum(List<Integer> lst) {
            if (lst == null) {
                return 0;
            }
            return lst.stream().mapToInt(Integer::intValue).sum();
        }

    }
}
